1. Field of the Invention
The invention relates in general to a decoder and associated decoding method for quasi-cyclic low-density parity-check (QC-LDPC) codes, and more particularly to a decoder comprising a parallel processing structure for QC-LDPC codes and associated decoding method.
2. Description of the Related Art
Along with rapid development of wireless transmission and communication technology, requirements for transmission bandwidth and efficiency also become stricter. The forward error correction is targeted at increasing transmission correctness and contributes noticeable improvement in increasing transmission efficiency, and is thus valued by developers. Under such trends, various methods and codes for forward error correction are proposed. Some of the well-known codes are the block code, the Hamming code, the convolutional code, the turbo code, and the low-density parity-check (LDPC) code that have attracted much attention in the last decade. In forward error correction applications, since the LDPC code approximates code performance of the Shannon limit, it is therefore an important branch for consideration.
The Shannon limit (or Shannon capacity) is defined as a coding rate in a communication channel which has a predetermined signal-to-noise ratio (SNR). In other words, the Shannon limit signifies a limitation (theoretical maximum) of the transmission capability (transfer rate) for a given communication channel at a particular noise level.
The LDPC code is a type of linear block error correcting code, where low-density indicates a ratio of the number of 1 in a check matrix relative to overall matrix elements is quite small, which is also the primary characteristic of low-density correction. The linear block code is a commonly implemented error correction code. According to the linear block code, a signal to be transmitted is multiplied with a generate matrix G to generate a transmission code longer than the original data. Upon receiving the signal, the signal is multiplied with a transposed check matrix H to check and correct the received data to restore the received signal information to the original data.
In an (n, k) LDPC code, n represents a codeword of the code, k represents a length of information bits, and the coding ratio of the LDPC code is defined as R=k/n by applying a defined check matrix. The check matrix is designated as regular, semi-regular, or irregular according to whether each column weight or row weight of the check matrix is the same. The column weight is based on the number of ones (“1”) in one column of the check matirx, and the row weight is based on the number of ones (“1”) in one row of the check matrix. A check matrix with a constant column weight and a constant row weight is defined as a regular check matrix; a check matrix with either a constant column weight or a constant row weight is defined as a semi-regular check matrix; a check matrix with no constant column weight or row weight is defined as an irregular check matrix. In terms of efficiency, performance of an irregular check matrix is the best, although associated hardware designs may suffer from complications due to its irregularity characteristic.
In currently promoted and specified terrestrial digital broadcast standards, e.g., China Mobile Multimedia Broadcasting (CMMB), Digital Terrestrial Multimedia Broadcast (DTMB), and Digital Video Broadcasting (DVB), including WiMax, IEEE802.11n, and IEEE802.3an, the LDPC code is promoted as a basis for forward error correction.
The LDPC code applied to the foregoing terrestrial digital broadcast is quasi-cyclic, and is so called a QC-LDPC code. A QC-LDPC code is defined by designating its corresponding parity-check matrices, and comprises a plurality of same-sized scattered cyclic matrices.
The QC-LDPC code is codeword-cyclic. More specifically, supposing the codeword C=(c0, c1, . . . , cN−1) is a qualified codeword (where N represents a length of the codeword), a codeword obtained by shifting S(0≦s≦N−1) elements to the right from the codeword C is still a qualified codeword. Quasi-cyclic is different from codeword-cyclic, which is merely partially cyclic. In other words, the QC-LDPC code is quasi-cyclic, with details to be described below.
Supposing the codeword c=(c1, c2, . . . , cn) is a qualified codeword of the QC-LDPC code, where a codeword N is nL, and a length of a vector cj=(cj, 0, cj, 1, . . . , cj, L−1)(1≦j≦n) is L, a codeword Tpc obtained from shifting a codeword c by p(0≦p≦L−1) elements along a right loop is still a qualified QC-LDPC codeword. The quasi-cyclic codeword Tpc=(˜Tpc1, ˜Tpc2, . . . , ˜Tpcn), means each vector cj is cyclically shifted to the right, that is, ˜Tpc=(cj, L−p, cj, L−p+1, . . . , cj, L−p−1).
Common LCPC decoding approaches perform algorithms using the natural logarithms base (logarithms with a base of e). Through logarithmic algorithms, multiplication operations are converted to addition and division operations are converted to subtraction, and indices are completely eliminated to leave performance of a decoder unaffected. However, complicated mathematical calculations are still required for logarithm algorithms in LDPC, for example:ln(ea+eb+ec+ . . . )
To reduce burden on the above indices and algorithms, a Jacobian formula is applied to simplify the calculations, as:max*(a,b)=ln(ea+eb)=max(a,b)+ln(1+e−|a-b|)
The Jacobian calculation is commonly referred to as the max* algorithm. For calculations involving a longer sum of indices, the Jacobian algorithm replaces calculations of sum of indices by addition, thereby significantly lowering complications in decoding.
In error detection realized by the QC-LDPC code, according to the terrestrial broadcasting specifications, a signal to be transmitted by a transmitting terminal is multiplied by a generate matrix to generate a transmission code longer than the original data. Upon receiving the signal at a receiving terminal, the transmitted code is multiplied with a transposed check matrix to check and correct the received data to restore the original data. Below is an example taking an original data of 4 bits, and transmission data of 7 bits.
At the transmitting terminal, the original data is multiplied by the generate matrix, as represented by an equation (1) below:
                                          [                                          d                1                            ⁢                                                          ⁢                              d                2                            ⁢                                                          ⁢                              d                3                            ⁢                                                          ⁢                              d                4                                      ]                    ×                      [                                                            1                                                  0                                                  0                                                  0                                                  1                                                  1                                                  0                                                                              0                                                  1                                                  0                                                  0                                                  1                                                  0                                                  1                                                                              0                                                  0                                                  1                                                  0                                                  0                                                  1                                                  1                                                                              0                                                  0                                                  0                                                  1                                                  1                                                  1                                                  1                                                      ]                          =                  [                                    e              1                        ⁢                                                  ⁢                          e              2                        ⁢                                                  ⁢                          e              3                        ⁢                                                  ⁢                          e              4                        ⁢                                                  ⁢                          e              5                        ⁢                                                  ⁢                          e              6                        ⁢                                                  ⁢                          e              7                                ]                                    (        1        )            
At the receiving terminal, the check matrix is defined as a transposed matrix of the generate matrix, and the original data is restored by decoding at the receiving terminal based on the characteristic that a product of the generate matrix and its transposed matrix is 0, as represented by an equation (2) below:
                                          [                                          e                1                ′                            ⁢                                                          ⁢                              e                2                ′                            ⁢                                                          ⁢                              e                3                ′                            ⁢                                                          ⁢                              e                4                ′                            ⁢                                                          ⁢                              e                5                ′                            ⁢                                                          ⁢                              e                6                ′                            ⁢                                                          ⁢                              e                7                ′                                      ]                    ×                      [                                                            1                                                  1                                                  0                                                                              1                                                  0                                                  1                                                                              0                                                  1                                                  1                                                                              1                                                  1                                                  1                                                                              1                                                  0                                                  0                                                                              0                                                  1                                                  0                                                                              0                                                  0                                                  1                                                      ]                          =                  {                                                                                                                e                      1                      ′                                        +                                          e                      2                      ′                                        +                                          e                      4                      ′                                        +                                          e                      5                      ′                                                        =                  0                                                                                                                                                e                      1                      ′                                        +                                          e                      3                      ′                                        +                                          e                      4                      ′                                        +                                          e                      6                      ′                                                        =                  0                                                                                                                                                e                      2                      ′                                        +                                          e                      3                      ′                                        +                                          e                      4                      ′                                        +                                          e                      7                      ′                                                        =                  0                                                                                        (        2        )            
Supposing no errors exist during the transmission process, a result of the equation (2) at the receiving terminal would render a zero vector. However, in the event that a non-zero vector is produced, it means that data received by the receiving end contains an error, and so the error is identified by check matrix algorithms and then corrected to achieve error correction.
Under a dilemma between decoding performance and hardware complexity, LDPC coding is generally realized by a partially parallel structure, in which a memory is utilized for storing exchanged information. The size of the memory is directly proportional to the number of binary ones (“1”) in a parity-check matrix (PCM). Since the memory needed for realizing LDPC decoding would occupy a considerably large area on an integrated circuit, it is then a vital task to reduce the area occupied by the memory in an LDPC decoder.
Taking the digital terrestrial broadcast applying QC-LDPC correction for decoding as example, a decoding structure of the prior art needs to concurrently process large amounts of data. For the DVB-T2 specifications, it is essential that a system should be capable of concurrently storing and performing high-speed algorithms over a 64800-bit matrix in order to decode information of one frame when the coding rate is 3/4. Therefore, apparently, even with parallel operations, huge amounts of system resources with high-speed processing ability are still required for processing the data amounts of the above matrix to satisfy a minimum update rate for dynamic display, meaning that costs need for realizing the DVB specifications are significantly increased.
Therefore, the present invention provides a decoder and associated decoding method for decoding QC-LDPC codes to overcome the above drawbacks associated with the prior art.